#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+100;
const int mod=10007;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL tree[maxn][26],fail[maxn],flag[maxn],pc=0,ans=0;
LL dp[maxn*26];
char str[maxn];
inline void ins(string& s){
    LL n=s.length();LL cur=0;
    for(int i=0;i<n;i++){
        LL c=s[i]-'a';
        if(!tree[cur][c]) tree[cur][c]=++pc;
        cur=tree[cur][c];
    }
    flag[cur]++;
}
inline void getfail(){
    queue<LL>que;
    fail[0]=0;
    for(int c=0;c<26;c++){
        LL u=tree[0][c];
        if(u){
            fail[u]=0;que.push(u);
        }
    }
    while(!que.empty()){
        LL r=que.front();que.pop();
        for(int c=0;c<26;c++){
            LL u=tree[r][c];
            if(!u) continue;
            que.push(u);
            LL v=fail[r];
            while(v&&!tree[v][c]) v=fail[v];
            fail[u]=tree[v][c];
        }
    }
}
inline LL dfs(LL tot){
    if(dp[tot]) return dp[tot];
    if(tot<=0) return 0;
    LL res=(flag[tot]+dfs(fail[tot])%mod)%mod;
    dp[tot]=res%mod;
    return res;
}
inline void fd(string& s){
    LL j=0;LL n=s.size();
    for(int i=0;i<n;i++){
        LL c=s[i]-'a';
        while(j&&!tree[j][c]) j=fail[j];
        j=tree[j][c];
        LL temp=j;
        ///tle
        while(temp!=0){
            ans=(ans+dfs(temp))%mod;
            break;
            ///ans=(ans+flag[temp])%mod;
            ///temp=fail[temp];

        }
    }
}
int main(void){
   	cin.tie(0);std::ios::sync_with_stdio(false);
    LL t;cin>>t;
    while(t--){
        LL n;cin>>n;
        cin>>str;
        string s;
        for(int i=0;i<n;i++){
            s+=str[i];
            ins(s);
        }
        getfail();
        fd(s);
        cout<<ans%mod<<endl;
        ans=0;
        pc=0;
        memset(tree,0,26*(n+2)*sizeof(LL));
        memset(fail,0,n*sizeof(LL));
        memset(flag,0,n*sizeof(LL));
    }
   	return 0;
}
